Close down Opera Mail and edit operaprefs.ini. See "Menu -> Help -> About Opera Mail" for the location. Under [User Prefs], make sure "Show Notification For New Messages" is NOT there so that Opera uses the default for the setting (which is 1). You can keep it there and set it to 1 if you want, but do the other way instead. Then, make sure you never mess with the checkbox in the settings UI as it's broken. It's really only broken for unchecking (trying to set it to 0), but just avoid the checkbox for good measure.
That's probably not going to help as you already get notifications sometimes. But, I'd try it just for good measure so that you know the setting is right.
Then, while Opera Mail is closed, for each account in question, check the section for the account in accounts.ini in the mail folder. You want Sound Enabled=1 set and Sound File=path to .wav file (make sure it's a .wav file).
That's probably not going to help either as it sounds like things are set correctly.
Then in the UI under the settings for each account, on the Incoming tab, make sure "Include this account when checking manually" is checked. Make sure "check every..." is checked and set it to less than 30 minutes (and no less than 10 if the server has a problem with you checking too frequently). You need to do that even if you're using IMAP and IDLE so the IDLE connection doesn't time out. You also need to make sure you're not using low-bandwidth mode.
If everything's good and you still have the issue, you're out of luck. It just happens for some people in Opera Mail and no one has ever figured out why.